package code.BinaryTree;

import struct.Tree;
import struct.TreeNode;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Serialization {

	public static void main(String[] args) {
		TreeNode tree = Tree.constructTree("[1,2,3,null,null,4,5]");
		Serialization serialization = new Serialization();
		String serialize = serialization.serialize(tree);
		System.out.println(serialize);
		StringBuilder sb = new StringBuilder();
		serialization.serialize(tree,sb);
		sb.delete(0,sb.length());
		String s = sb.toString();
		System.out.println(s);

		TreeNode deserialize = serialization.deserialize(serialize);

		System.out.println(deserialize);


		TreeNode treeNode = serialization.bstFromPreorder(new int[]{8, 5, 1, 7, 10, 12});
		System.out.println(treeNode);

		tree = Tree.constructTree("[1,2,3,null,4]");
		List<List<String>> lists = serialization.printTree(tree);
		System.out.println(lists);

		TreeNode node = serialization.constructMaximumBinaryTree(new int[]{3, 2, 1, 6, 0, 5});
		System.out.println(node);
		TreeNode node1 = serialization.constructMaximumBinaryTree2(new int[]{3, 2, 1, 6, 0, 5});
		System.out.println(node1);
		System.out.println();

		int numTrees = serialization.numTrees(5);
		System.out.println(numTrees);
		int numTrees2 = serialization.numTrees2(5);
		System.out.println(numTrees2);


		System.out.print("998. 最大二叉树 II");
		TreeNode tre = Tree.constructTree("[5,2,4,null,1]");
		serialization.insertIntoMaxTree(tre, 3);
	}

	// Encodes a tree to a single string.
	public String serialize(TreeNode root) {
		if (root == null) {
			return "null,";
		}
		String nStr = root.val + ",";
		String lStr = serialize(root.left);
		String rStr = serialize(root.right);
		return nStr + lStr + rStr;
	}

	public void serialize(TreeNode root, StringBuilder sb) {
		if (root == null) {
			sb.append("null,");
			return;
		}
		sb.append(root.val).append(",");
		serialize(root.left, sb);
		serialize(root.right, sb);
	}

	// Decodes your encoded data to tree.
	public TreeNode deserialize(String data) {
		String[] split = data.split(",");
		return deserializeHelper(split, new int[1]);
	}

	public TreeNode deserializeHelper(String[] strs, int[] cur) {
		if (cur[0] == strs.length || strs[cur[0]].equals("null")) {
			return null;
		}
		TreeNode head = new TreeNode(Integer.parseInt(strs[cur[0]]));
		cur[0]++;
		head.left = deserializeHelper(strs, cur);
		cur[0]++;
		head.right = deserializeHelper(strs, cur);
		return head;
	}

	//1008. 先序遍历构造二叉树
	public TreeNode bstFromPreorder(int[] preorder) {
		return bstFromPreorderHelper(preorder, 0, preorder.length - 1);
	}

	public TreeNode bstFromPreorderHelper(int[] preorder, int left, int right) {
		if (left > right) {
			return null;
		}
		TreeNode treeNode = new TreeNode(preorder[left]);
		int mid = left;
		for (int i = left + 1; i < preorder.length; i++) {
			if (preorder[i] > preorder[left]) {
				break;
			}
			mid++;
		}

		treeNode.left = bstFromPreorderHelper(preorder, left + 1, mid);
		treeNode.right = bstFromPreorderHelper(preorder, mid + 1, right);
		return treeNode;
	}

	// 655. 输出二叉树
	public List<List<String>> printTree(TreeNode root) {
		List<List<String>> arrayList = new ArrayList<>();
		int h = printTreeHeightHelper(root);
		int w = (int) (Math.pow(2, h) - 1);
		String[][] strings = new String[h][w];
		for (String[] string : strings) {
			Arrays.fill(string, "");
		}
		printTreeHeper(root, strings, 0, w - 1, 0);
		for (String[] string : strings) {
			arrayList.add(Arrays.asList(string));
		}
		return arrayList;
	}

	public void printTreeHeper(TreeNode root, String[][] strings, int left, int right, int h) {
		if (root == null) {
			return;
		}
		int mid = left + (right - left) / 2;
		strings[h][mid] = "" + root.val;
		printTreeHeper(root.left, strings, left, mid - 1, h + 1);
		printTreeHeper(root.right, strings, mid + 1, right, h + 1);
	}

	public int printTreeHeightHelper(TreeNode root) {
		if (root == null) {
			return 0;
		}
		return Math.max(printTreeHeightHelper(root.left), printTreeHeightHelper(root.right)) + 1;
	}

	//998. 最大二叉树 II
	public TreeNode insertIntoMaxTree(TreeNode root, int val) {
		TreeNode head = new TreeNode(0);
		head.right = root;
		TreeNode pre = head;
		TreeNode cur = root;
		while (cur != null && cur.val > val) {
			pre = cur;
			cur = cur.right;
		}
		TreeNode node = new TreeNode(val);
		node.left = cur;
		pre.right = node;
		return head.right;
	}

	// 654. 最大二叉树2
	public TreeNode constructMaximumBinaryTree2(int[] nums) {
		if (nums == null || nums.length == 0) {
			return null;
		}
		TreeNode head = new TreeNode(nums[0]);
		for (int i = 1; i < nums.length; i++) {
			head = insertIntoMaxTree(head, nums[i]);
		}
		return head;
	}

	//	654. 最大二叉树
	public TreeNode constructMaximumBinaryTree(int[] nums) {
		if (nums == null || nums.length == 0) {
			return null;
		}
		return constructMaximumBinaryTreeH(nums, 0, nums.length);
	}

	public TreeNode constructMaximumBinaryTreeH(int[] nums, int start, int end) {
		if (start >= end) {
			return null;
		}

		int maxVal = 0;
		int maxI = start;
		for (int i = start; i < end; i++) {
			if (nums[i] > maxVal) {
				maxVal = nums[i];
				maxI = i;
			}
		}

		TreeNode node = new TreeNode(nums[maxI]);
		node.left = constructMaximumBinaryTreeH(nums, start, maxI);
		node.right = constructMaximumBinaryTreeH(nums, maxI + 1, end);
		return node;
	}

	//96.不同的二叉搜索树
	public int numTrees(int n) {
		if (n == 0) {
			return 0;
		}
		return numsTreesH(1, n, new HashMap<Integer, Integer>());
	}

	public int numsTreesH(int start, int end, HashMap<Integer, Integer> hashMap) {
		if (start > end) {
			return 1;
		}
		int length = end - start + 1;
		Integer integer = hashMap.get(length);
		if (integer != null) {
			return integer;
		}
		int sum = 0;
		for (int i = start; i <= end; i++) {
			int lNums = numsTreesH(start, i - 1, hashMap);
			int rNums = numsTreesH(i + 1, end, hashMap);
			sum += lNums * rNums;

		}
		hashMap.put(length, sum);
		return sum;
	}

	public int numTrees2(int n) {
		int[] G = new int[n + 1];
		G[0] = 1;
		G[1] = 1;
		for (int j = 2; j <= n; j++) {
			for (int i = 1; i <= j; i++) {
				G[j] += G[i - 1] * G[j - i];
			}
		}
		return G[n];
	}
}
